lib/Mi manual de algoritmos/version_maraton_nacional_2008/src/grafos/puntos_articulacion.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$set$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$map$>$}} \\
   8 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
   9 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
  10 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iterator$>$}} \\
  11 \mbox{} \\
  12 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
  13 \mbox{} \\
  14 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ string\ node\textcolor{BrickRed}{;} \\
  15 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ map\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$}\ graph\textcolor{BrickRed}{;} \\
  16 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ \textcolor{ForestGreen}{char}\ color\textcolor{BrickRed}{;} \\
  17 \mbox{} \\
  18 \mbox{}\textbf{\textcolor{Blue}{const}}\ color\ WHITE\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ GRAY\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{1}\textcolor{BrickRed}{,}\ BLACK\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  19 \mbox{} \\
  20 \mbox{}graph\ g\textcolor{BrickRed}{;} \\
  21 \mbox{}map\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{,}\ color\textcolor{BrickRed}{$>$}\ colors\textcolor{BrickRed}{;} \\
  22 \mbox{}map\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\textcolor{BrickRed}{$>$}\ d\textcolor{BrickRed}{,}\ low\textcolor{BrickRed}{;} \\
  23 \mbox{} \\
  24 \mbox{}set\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$}\ cameras\textcolor{BrickRed}{;} \\
  25 \mbox{} \\
  26 \mbox{}\textcolor{ForestGreen}{int}\ timeCount\textcolor{BrickRed}{;} \\
  27 \mbox{} \\
  28 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{dfs}}\textcolor{BrickRed}{(}node\ v\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{bool}\ isRoot\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  29 \mbox{}\ \ colors\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ GRAY\textcolor{BrickRed}{;} \\
  30 \mbox{}\ \ d\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ low\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{++}timeCount\textcolor{BrickRed}{;} \\
  31 \mbox{}\ \ vector\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$}\ neighbors\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{];} \\
  32 \mbox{}\ \ \textcolor{ForestGreen}{int}\ count\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}neighbors\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  34 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}colors\textcolor{BrickRed}{[}neighbors\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{==}\ WHITE\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textit{\textcolor{Brown}{//\ \ (v,\ neighbors[i])\ is\ a\ tree\ edge}} \\
  35 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{dfs}}\textcolor{BrickRed}{(}neighbors\textcolor{BrickRed}{[}i\textcolor{BrickRed}{],}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{);} \\
  36 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(!}isRoot\ \textcolor{BrickRed}{\&\&}\ low\textcolor{BrickRed}{[}neighbors\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{$>$=}\ d\textcolor{BrickRed}{[}v\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  37 \mbox{}\ \ \ \ \ \ \ \ cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
  38 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  39 \mbox{}\ \ \ \ \ \ low\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\textcolor{BrickRed}{(}low\textcolor{BrickRed}{[}v\textcolor{BrickRed}{],}\ low\textcolor{BrickRed}{[}neighbors\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]);} \\
  40 \mbox{}\ \ \ \ \ \ \textcolor{BrickRed}{++}count\textcolor{BrickRed}{;} \\
  41 \mbox{}\ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{}\ \textit{\textcolor{Brown}{//\ (v,\ neighbors[i])\ is\ a\ back\ edge}} \\
  42 \mbox{}\ \ \ \ \ \ low\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\textcolor{BrickRed}{(}low\textcolor{BrickRed}{[}v\textcolor{BrickRed}{],}\ d\textcolor{BrickRed}{[}neighbors\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]]);} \\
  43 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  44 \mbox{}\ \ \textcolor{Red}{\}} \\
  45 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}isRoot\ \textcolor{BrickRed}{\&\&}\ count\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{1}\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textit{\textcolor{Brown}{//Is\ root\ and\ has\ two\ neighbors\ in\ the\ DFS-tree}} \\
  46 \mbox{}\ \ \ \ cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
  47 \mbox{}\ \ \textcolor{Red}{\}} \\
  48 \mbox{}\ \ colors\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ BLACK\textcolor{BrickRed}{;} \\
  49 \mbox{}\textcolor{Red}{\}} \\
  50 \mbox{} \\
  51 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  52 \mbox{}\ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{;} \\
  53 \mbox{}\ \ \textcolor{ForestGreen}{int}\ map\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
  54 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}cin\ \textcolor{BrickRed}{$>$$>$}\ n\ \textcolor{BrickRed}{\&\&}\ n\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  55 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}map\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{1}\textcolor{BrickRed}{)}\ cout\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
  56 \mbox{}\ \ \ \ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  57 \mbox{}\ \ \ \ colors\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  58 \mbox{}\ \ \ \ d\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  59 \mbox{}\ \ \ \ low\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  60 \mbox{}\ \ \ \ timeCount\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  61 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}n\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
  62 \mbox{}\ \ \ \ \ \ node\ v\textcolor{BrickRed}{;} \\
  63 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ v\textcolor{BrickRed}{;} \\
  64 \mbox{}\ \ \ \ \ \ colors\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ WHITE\textcolor{BrickRed}{;} \\
  65 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ vector\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$();} \\
  66 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  67 \mbox{}\ \ \ \  \\
  68 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ n\textcolor{BrickRed}{;} \\
  69 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}n\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
  70 \mbox{}\ \ \ \ \ \ node\ v\textcolor{BrickRed}{,}u\textcolor{BrickRed}{;} \\
  71 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ v\ \textcolor{BrickRed}{$>$$>$}\ u\textcolor{BrickRed}{;} \\
  72 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{);} \\
  73 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}u\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
  74 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  75 \mbox{}\ \ \ \  \\
  76 \mbox{}\ \ \ \ cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{clear}}\textcolor{BrickRed}{();} \\
  77 \mbox{}\ \ \ \  \\
  78 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}graph\textcolor{BrickRed}{::}iterator\ i\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{();}\ i\ \textcolor{BrickRed}{!=}\ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  79 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}colors\textcolor{BrickRed}{[(*}i\textcolor{BrickRed}{).}first\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ WHITE\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  80 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Black}{dfs}}\textcolor{BrickRed}{((*}i\textcolor{BrickRed}{).}first\textcolor{BrickRed}{);} \\
  81 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  82 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  83 \mbox{}\ \ \ \ \ \  \\
  84 \mbox{}\ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{}City\ map\ \#"{}}}\textcolor{BrickRed}{$<$$<$}map\textcolor{BrickRed}{$<$$<$}\texttt{\textcolor{Red}{"{}:\ "{}}}\ \textcolor{BrickRed}{$<$$<$}\ cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{}\ camera(s)\ found"{}}}\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
  85 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{copy}}\textcolor{BrickRed}{(}cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ cameras\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{(),}\ ostream$\_$iterator\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$(}cout\textcolor{BrickRed}{,}\texttt{\textcolor{Red}{"{}}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{));} \\
  86 \mbox{}\ \ \ \ \textcolor{BrickRed}{++}map\textcolor{BrickRed}{;} \\
  87 \mbox{}\ \ \textcolor{Red}{\}} \\
  88 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  89 \mbox{}\textcolor{Red}{\}} \\
  90
  91 } \normalfont\normalsize